package com.xzx.maxsublistsum;

/**
 * 最大连续子列和
 * @author xinzhixuan
 * @version V1.0.0
 * @date 2021/3/3
 **/
public class MaxSubListSum {
    public static void main(String[] args) {

//        int[] arr = {-6, 7, 4, -3, 1};
        int[] arr = {-6, -3};
//        int[] arr = {-6, 7, -1, 4};
//        System.out.println(getSum01(arr));
//        System.out.println(getSum02(arr));
//        System.out.println(getSum03(arr));
        System.out.println(getSum04(arr));
    }

    /**
     * 方法4获取最大子列和，使用在线处理逻辑，来一个实时计算一个,借助负数对和没有共享的特性
     * 复杂度  O(N)
     * @param arr .
     * @return .
     */
    public static int getSum04(int[] arr) {
        int thisSum = 0;
        int maxSum = arr[0];
        for (int j : arr) {
            thisSum += j;
            if (thisSum > maxSum) {
                maxSum = thisSum;
            } else if (thisSum < 0) {// 说明连续的半截加起来都是负数，对后面的和没有贡献 ，这块直接从0重新开始加
                thisSum = 0;
            }
        }
        return maxSum;
    }

    /**
     * 方法3获取最大子列和，使用分而治之的思路计算
     * 复杂度  O(nlogn)  n^2的算法都可以考虑优化为nlogn
     * @param arr .
     * @return .
     */
    public static int getSum03(int[] arr) {
        if (arr.length == 0) {
            throw new RuntimeException("子列是空的");
        }
        return recursionCalculate(arr, 0, arr.length - 1);
    }

    private static int recursionCalculate(int[] arr, int left, int right) {
        if (left == right) {
            return arr[left];
        }

        int middle = (left + right) / 2;
        // 左侧序列的最大子列和
        int leftSubListMaxSum = recursionCalculate(arr, left, middle);
        // 右侧序列的最大子列和
        int rightSubListMaxSum = recursionCalculate(arr, middle + 1, right);

        //中间往左侧计算的最大和
        int leftThisSum = 0;
        int leftMaxSum = Integer.MIN_VALUE;
        for(int i = middle; i >= left; i--) {
            leftThisSum += arr[i];
            if (leftThisSum > leftMaxSum) {
                leftMaxSum = leftThisSum;
            }
        }

        //中间往右侧计算的最大和
        int rightThisSum = 0;
        int rightMaxSum = Integer.MIN_VALUE;
        for (int i = middle+1; i <= right; i++) {
            rightThisSum += arr[i];
            if (rightThisSum > rightMaxSum) {
                rightMaxSum = rightThisSum;
            }
        }

        return Math.max(leftSubListMaxSum, Math.max(rightSubListMaxSum, leftMaxSum + rightMaxSum));
    }


    /**
     * 方法2获取最大子列和，相比较方法一，不需穷举完所有的子列集
     * 复杂度  O(n^2)
     * @param arr .
     * @return .
     */
    public static int getSum02(int[] arr) {
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0; i< arr.length; i++) {
            int thisSum = 0;
            for(int j = i; j < arr.length; j++) {
                thisSum += arr[j];
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                }
            }
        }
        return maxSum;
    }

    /**
     * 方法1获取最大子列和
     * 使用暴力方式获取,三层循环，群举出所有的连续子列，然后计算最大的和   复杂度  O(n^3)
     * @param arr .
     * @return .
     */
    public static int getSum01(int[] arr) {
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0; i< arr.length; i++) {
            for(int j = i; j < arr.length; j++) {
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += arr[k];
                }
                if (sum > maxSum) {
                    maxSum = sum;
                }
            }
        }
        return maxSum;
    }
}
